Image databases are databases that contain digital data of images and are finding ever-increasing uses in business and entertainment. The widespread use of image databases, however, is intensifying the need to develop more effective ways of searching such databases.
By way of background, a database is a collection of related data. Oftentimes, the data in a database is structurally organized as tables, fields and records. Generally, each record in the database possesses a set of attributes and a user may wish to conduct a search of the database based upon a value of one or more of the attributes. For example, in a database of football statistics, one may desire to search for all quarterbacks who completed 100 or more passes in a single season, etc.
In conducting such a search, it is assumed that each record possesses several attributes and the user wants to search for all records that possess certain values of certain attributes. The specification of which records are desired is called a query and is usually restricted to one of three types: a) A simple query which specifies a specific value for a specific attribute; e.g., THROWINGARM=LEFT; or THROWINGARM=RIGHT; b) a range which specifies a specific range of values for a specific attribute; e.g., WEIGHT&lt;220 or, 180&lt;WEIGHT&lt;220; and c) a BOOLEAN such as (THROWINGARM=LEFT) AND (HEIGHT&gt;6') and (COMPLETIONS&gt;99)).
Unfortunately, such query-based methods do not permit one to effectively search an image database because: (1) image data is generally not well annotated with textual attribute descriptions, and (2) the vocabulary needed to describe a user's query may not exist or at least not be know to the user. Consequently, the prior art has shown an increasing interest in developing image search and retrieval methods.
At present, there exist several principal approaches to image retrieval from databases.
1. Browsing and navigational searching: In this approach, users are presented with directories wherein each directory contains a single category of images (e.g. business, people, and plants). The users navigate through the directories and select a particular one in which to browse, generally containing images of a similar category. PA0 2. Syntactic keyword searching: Using this approach, users input keywords and are subsequently presented with the images whose captions or keyword lists contain the specified keyword(s). PA0 3. Descriptive semantics searching: With descriptive semantics searching, users specify semantics of the image they want to retrieve. This approach requires the semantics of the query and images to be explicit so that the query processor can determine the similarity. A scene-based image retrieval can be viewed as a type of semantics-based search. An example query of this type of search would be "Retrieve images in which there is a man next to a tree." PA0 4. Cognition-based search: The cognition-based search supports queries by content semantics. Users pose queries by providing drawings or image examples. The system retrieves images which are similar to the example provided by the user. For example, a user may pose a query by drawing a picture where there is a man next to a building, and the system would retrieve images similar to his drawing.
Numerous prior-art methods and systems attempting to overcome the drawbacks associated with image searching and utilizing one or more components of the above methods have been described. One such system is the COIR (Content-Oriented Image Retrieval) system which was described in an article entitled "Content-Oriented Integration in Hypermedia Systems", authored by K. Hirata, Y. Hara, H. Takano, and S. Kawasaki and which appeared in the Proceedings of 1996 ACM Conference on Hypertext in March, 1996. COIR utilizes an image retrieval technique based upon a set of features extracted from images, such as colors and shapes. Unlike most other existing approaches, where feature extraction and image matching techniques are based on the whole image, COIR's feature extraction and image matching techniques are object-based.
Another prior-art system, Virage, which was described by J. R. Bach, C. Fuller, A. Gupta, A. Hampapur, B. Horowitz, R. Jain and C. F. Shu in an article entitled "The Virage Image Search Engine: An Open Framework for Image Management" which appeared in Proceedings of the SPIE--The International Society for Optical Engineering: Storage and Retrieval for Still Images and Video Databases, 1993, is a system for image retrieval based on visual features, or image "primitives". These primitives can be general, such as color, shape, or texture, or domain specific. Virage transforms images from a data-rich representation of explicit image pixels to a more compact, semantic-rich representation of visually salient characteristics. These primitives are then used to solve specific image management problems.
The QBIC (Query By Image Content) system which was described by W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, and G. Taubin in an article entitled "The QBIC Project: Quering Images by Content Using Color, Texture, and Shape", which appeared in Proceedings of the SPIE: Storage and Retrieval for Images and Video Databases, 1993, is a system for image retrieval. It allows users to query an image collection using features of image contents, such as color, texture, shape, location, and layout of images. With the QBIC system, queries are formed graphically.
Finally, the SCORE system which was described by Y. Aslandogan, C. Yu, C. Liu and K. Nair in an article entitled "Similarity based Retrieval of Pactures Using Indices on Spatial Relationships" which appeared in Proceedings of the 1995 VLDB Conference, held in Zurich, Switzerland in 1995, is a system for similarity-based image retrieval. This system using a refined ER model to represent the contents of pictures and the calculation of similarity values based on such representations. Users can use icons to specify objects, say man and phone, and then specify their relationship to one another.
Despite the relative advantages associated with each of the above approaches however, each presents a set drawbacks and limitations as well. Specifically, the semantics-based approach is good at image retrieval based on image semantics. However, since images are visual and hard to describe in detail using only text, this approach suffers from a low visual expressive capability. Another weakness of the semantics-based approach is that the semantics of images must be specified explicitly before the search is performed.
The cognition-based approach, on the other hand, advantageously uses visual examples. Unfortunately, user generated drawings tend to be rather imprecise thereby leading to search ambiguity. Consequently, if a user of a cognition based system wanted to retrieve all of the images in a database containing a taxi, this approach would likely retrieve a very large number of images with cars, but not necessarily taxis. A further weakness of this cognition approach is that it can not support queries on generalized concepts. For example, if a user wants to retrieve all images in which there is some kind of an appliance, the user must provide drawings for all possible appliances, such as TVs, radios, computers, and CD players. As such, it is simply not practical for most applications.
Consequently, a continuing need exists in the art for techniques which provide for the efficient searching of images contained within a database of images.